Now that we've seen how to identify an MST by its minimum total weight, let's explore the fundamental rules that all Minimum Spanning Trees must follow. These properties are critical for understanding how MST algorithms work.
- Any spanning tree for a graph with $V$ vertices will always contain exactly $V-1$ edges. Adding one more edge creates a cycle, and removing one disconnects the graph.
- The total weight of an MST is unique for a given graph. However, the MST itself is not always unique. If a graph has multiple edges with the same weight, it's possible to have several different MSTs that share the same minimum total weight.
| Property | Description |
|---|---|
| Number of Edges | An MST for a graph with $V$ vertices will always have exactly $V-1$ edges. |
| Weight Uniqueness | For a given graph, the total weight of an MST is always unique. |
| Tree Uniqueness | The MST is only guaranteed to be unique if all edge weights in the graph are distinct. |